\section{Description du problème}
\label{descr-prob}
Ce que nous donne la distribution, c'est un graphe coloré où chaque couleur est associée à un site et o\`u chaque noeud est associé à une instruction ou une variable. Dans un premier temps, ce dont nous avons besoin, c'est de pouvoir comparer deux graphes (celui de l'ancienne version du programme et celui de la nouvelle version) afin de repérer les modifications qui ont été effectuées sur le code. Ceci pourra donc nous permettre de savoir quels sont les noeuds qui ont été ajoutés, modifiés ou encore supprimés. \\

A ce stade, deux possibilités s'offrent à nous: soit nous décidons de ne re-colorier que les noeuds modifiés et ajoutés, soit nous décidons de re-vérifier l'ensemble des noeuds. En effet, il se peut que certaines instructions aient reçu une certaine couleur suite à une contrainte venant d'une autre instruction. Si cette dernière a été retirée, la contrainte de la couleur n'a plus lieu d'être, et nous pourrions trouver une meilleure assignation pour les instructions restantes. Dans ce travail, les deux possibilités seront étudiées et comparées afin de déterminer la meilleure manière de faire. \\

Après cette étape, il ne restera que les noeuds modifiés (et certains anciens qui n'auraient plus de contraintes sur leur précédente couleur) à re-colorier. Vient alors le problème de savoir comment nous allons les colorier de manière efficace, en gardant les propriétés atomiques des blocs \texttt{WHEN} et des instructions ainsi qu'en ne transmettant qu'un minimum de messages entre ces sites. \\

Dans les paragraphes qui suivent, je détaillerai un peu plus chacun des problèmes évoqués ci-dessus et je présenterai une piste pour tenter de trouver une solution à ceux-ci. \\

\subsection{Comparaison de graphes}
\label{sec-comp-graph}
Dans la théorie des graphes, en informatique, deux problématiques étudiées pourraient se rapprocher de notre premier problème. Il s'agit du mineur d'un graphe (\cite{MiGr}) et du problème du sous-graphe isomorphe (\cite{SuGr}). \\
Vous trouverez, ci-dessous, les définitions des notions importantes pour la compréhension de ces deux problèmes.

\begin{definition}
        Dans un graphe $G$, la contraction d'un arc $e$, ayant comme extrémités $u$ et $v$, est le remplacement de $u$ et $v$ par un seul et même noeud dont les arcs qui relient ce nouveau noeud au reste du graphe sont les arcs des noeuds $u$ et $v$, excepté $e$.
\end{definition}

\begin{definition}
	Un graphe $G$ est dit \textsl{isomorphe} à un graphe $H$ s'il existe une bijection entre les ensembles de noeuds de $G$ et $H$
	\begin{center}
		$f: V(G) \rightarrow V(H)$
	\end{center}
	telle que deux noeuds $u$ et $v$ de $G$ sont adjacents dans $G$ si et seulement si $f(u)$ et $f(v)$ sont adjacents dans $H$.
\end{definition}

\noindent
Maintenant, donnons une description des deux problèmes:
\begin{description}
	\item[Mineur d'un graphe.] Un graphe $G$ est le mineur d'un graphe $H$ si $G$ peut être obtenu suite à une ou plusieurs opérations (telles que des contractions et/ou des suppressions) sur les arcs du graphe.
	\begin{figure}
		\begin{center}
			\includegraphics[scale=0.5]{Images/minor.png}
			\caption{Exemple du mineur d'un graphe}
			\label{fig-minor}
		\end{center}
	\end{figure}
	Un exemple, venant de~\cite{MiGr}, est illustré sur la figure~\ref{fig-minor}, expliquons cet exemple. \\ 
	Soient trois graphes. Le premier est celui de $G$, le second celui de $H$ et le dernier est celui qui montre les opérations sur les arcs à effectuer. En effet, si nous supprimons les arcs et le noeud en pointillé et que nous fusionnons l'arc en gris clair, nous obtenons le graphe $G$.
	\item[Problème du sous-graphe isomorphe.] Partant de deux graphes, $G$ et $H$, le but est de déterminer si $G$ contient un sous-graphe qui est isomorphe à $H$. \\
\end{description}

Ces deux notions pourraient nous être utiles pour trouver d'éventuelles modifications de graphe, mais nous verrons ceci plus en détail ultérieurement.

\subsection{Re-coloration des anciens noeuds non modifiés}
Après avoir détecté les similitudes entre les deux graphes, nous devons re-colorier les noeuds inchangés dans la couleur qu'ils avaient avant la modification. Mais, pour garder le côté efficace de la distribution (avec un minimum de messages à transmettre entre les sites), nous pourrions décolorer certains noeuds afin de leur trouver une meilleure assignation de couleur. Illustrons ceci par un exemple: \\
Imaginons le bout de code suivant, reprenant un \texttt{WHEN}: 
\begin{verbatim}
	01:   WHEN a THEN
	02:       c := b;
	03:       b := b + 1;
	04:       a := FALSE;
	05:   END_WHEN
\end{verbatim}
Dans la table de localisation, parmi les trois variables, seule \texttt{c} est assignée à un certain site, ce qui impose à toutes les instructions du \texttt{WHEN} d'être sur le même site que \texttt{c} et donc, dans le graphe, ces noeuds auront la même couleur. Imaginons, maintenant, que nous voulons retirer l'instruction \texttt{02}. La seule contrainte de couleur imposée par \texttt{c} sur les autres instructions du bloc disparaît. \\
C'est dans un tel cas que nous voudrions chercher à trouver une meilleure assignation de couleur pour les instructions du bloc. \\

Maintenant, la question est de savoir comment détecter cette élimination de contrainte sur des instructions. Définissons d'abord la notion de \textsl{chemin} et de \textsl{composant connecté} dans un graphe:
\begin{definition}
	Un chemin, dans un graphe, est une suite de noeuds tel que de chaque noeud part un arc vers le noeud suivant dans la séquence.
\end{definition}
\begin{definition}
	Un composant connecté est un sous-graphe $H$ d'un graphe tel que chaque paire de noeuds de $H$ est reliée par un chemin.
\end{definition}
Clairement, les instructions d'un bloc \texttt{WHEN} ainsi que les instructions d'un bloc séquentiel utilisant des variables se retrouvant dans le bloc \texttt{WHEN} sont des composants connectés dans notre graphe. Nous pourrions, dès lors, trouver un moyen de connaître, dans un composant connecté, le noeud qui impose la couleur aux autres et ainsi détecter qu'un composant connecté n'a plus de contrainte liée à sa couleur.

\subsection{Coloration des noeuds modifiés et ajoutés}
Nous sommes au point o\`u le graphe de la nouvelle version du code est partiellement coloré. Il ne reste plus que les nouveaux noeuds, les noeuds modifiés et les noeuds décolorés auxquels nous devons assigner une couleur. Comment compléter la coloration de telle manière que les propriétés d'atomicité et d'efficacité soient respectées ? Ce problème se rapproche fortement de celui étudié dans~\cite{CoCoCo} qui, en partant d'un graphe partiellement coloré, se demande comment compléter la coloration telle que chaque couleur induit un certain nombre de composants connectés. Cela pourrait nous être utile afin de respecter la propriété d'atomicité des instructions, mais il faudrait adapter notre graphe afin que la propriété d'efficaté soit, elle aussi, respectée. \\

Dans le chapitre suivant, nous étudierons les différents sous-problèmes décrits ci-dessus et nous comparerons les deux possibilités, telles que décrites dans le second paragraphe de la section~\ref{descr-prob}.